400D - Dima and Bacteria - CodeForces Solution

// Problem: D. Dima and Bacteria
// Contest: Codeforces - Codeforces Round 234 (Div. 2)
// URL: https://codeforces.com/contest/400/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms

/*
	Author: MikiMiku
	
	Observation:
	
	Idea: 
		
*/

#include <bits/stdc++.h>
using namespace std;

/* DEBUGGING */
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

/* CONTAINER SHORTCUT */
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back 
#define eb emplace_back 
#define mp make_pair

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

/* GLOBAL OVERWRITE */
//#define int long long
#define endl '\n'

/* BIT MANIPULATION */
#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define LSB(S) (S & (-S))
#define setAll(S, n) (S = (1 << n) - 1)
#define modulo(S, N) ((S) & (N - 1))   // returns S % N, where N is a power of 2
#define isPowerOfTwo(S) (!(S & (S - 1)))
#define nearestPowerOfTwo(S) ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))
#define turnOffLastBit(S) ((S) & (S - 1))
#define turnOnLastZero(S) ((S) | (S + 1))
#define turnOffLastConsecutiveBits(S) ((S) & (S + 1))
#define turnOnLastConsecutiveZeroes(S) ((S) | (S - 1))

/* GEOMETRY */
typedef complex<double> Point;

/* TYPE RE-DEFINE */
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

/* CONSTANT */
const int MAX_N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const int FMOD = 998244353; 
const ll INF = 1e9 + 3;
const ld EPS = 1e-9;
const double PI=acos(-1);

/* SHORTCUT */
#define fi first
#define se second
typedef pair<int, int> ii;  
typedef vector<ii> vii;
typedef vector<int> vi;
typedef map<int,int> mii; 

/* RANDOM */
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG); 


//FLOAT PRECISION SETTINGS
/*
cout.setf(ios::fixed,ios::floatfield);
cout.precision(3);
*/
//FILE IO
void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

//........................................................................

const int lim = 1e5;
int par[lim + 7], renk[lim + 7];

int findSet(int u) {
	if(u == par[u]) return u;
	else return par[u] = findSet(par[u]);
}

bool isSameSet(int u, int v) {
	if(findSet(u) == findSet(v)) return true;
	else return false;
}

void UnionFind(int u, int v) {
	u = findSet(u); v = findSet(v);
	if(u != v) {
		if(renk[u] < renk[v]) swap(u, v);
		
		par[v] = u;
		if(renk[u] == renk[v]) renk[u]++;
	}
}

signed main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr); cout.tie(nullptr);
	int n, m, k;
	cin >> n >> m >> k;
	
	vector<int> ta;
	for(int i = 0; i < k; ++i) {
		int ci;
		cin >> ci;
		if(ta.empty()) ta.pb(ci);
		else ta.pb(ta.back() + ci);
	}
	
	for(int i = 1; i <= n; ++i) par[i] = i;
	memset(renk, 0, sizeof(renk));
	
	int tadj[507][507];
	for(int i = 0; i < k; ++i) {
		for(int j = 0; j < k; ++j) {
			if(i == j) tadj[i][j] = 0;
			else tadj[i][j] = INF;
		}
	}
	
	for(int i = 0; i < m; ++i) {
		int u, v, c;
		cin >> u >> v >> c;
		
		auto itu = lower_bound(all(ta), u);
		int t_u = itu - ta.begin();
		auto itv = lower_bound(all(ta), v);
		int t_v = itv - ta.begin();
		
		if(c == 0) UnionFind(u, v);
		if(t_u != t_v) {
			if(c < tadj[t_u][t_v]) {
				tadj[t_u][t_v] = c;
				tadj[t_v][t_u] = c;
			}
		}
 	}
 	
 	map<int, set<int>> mc;
 	for(int i = 1; i <= n; ++i) {
 		findSet(i);
 		auto it = lower_bound(all(ta), i);
 		int t = it - ta.begin();
 		mc[t].insert(par[i]);
 	}
 	for(auto p : mc) {
 		if(sza(p.se) > 1) {
 			cout << "No" << endl;
 			return 0;
 		}
 	}
 	
 	for(int l = 0; l < k; ++l) {
 		for(int i = 0; i < k; ++i) {
 			for(int j = 0; j < k; ++j) {
 				tadj[i][j] = min(tadj[i][j], tadj[i][l] + tadj[l][j]);
 			}
 		}
 	}
 	
 	cout << "Yes" << endl;
 	for(int i = 0; i < k; ++i) {
 		for(int j = 0; j < k; ++j) {
 			if(tadj[i][j] == INF) {
 				cout << -1 << " ";
 			} else cout << tadj[i][j] << " ";
 		} cout << endl;
 	}
 	
	return 0;
}